// 给定一个二叉树，在树的最后一行找到最左边的值。

// 示例 1:

// 输入:

//     2
//    / \
//   1   3

// 输出:
// 1
//  

// 示例 2:

// 输入:

//         1
//        / \
//       2   3
//      /   / \
//     4   5   6
//        /
//       7

// 输出:
// 7
//  

// 注意: 您可以假设树（即给定的根节点）不为 NULL。

#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/* 从右向左，从上向下，到最后一定是最后一行最左边
*/
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q{};
        q.push(root);
        TreeNode* node{nullptr};
        while (!q.empty()) {
            node = q.front();
            q.pop();
            if (node->right) q.push(node->right);
            if (node->left) q.push(node->left);
        }
        return node->val;
    }
};

class Solution {
public:
    void dfs(TreeNode *root, int height, int &curVal, int &curHeight) {
        if (root == nullptr) {
            return;
        }
        ++height;
        dfs(root->left, height, curVal, curHeight);
        dfs(root->right, height, curVal, curHeight);
        if (height > curHeight) {
            curHeight = height;
            curVal = root->val;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        int curVal = 0;
        int curHeight = 0;
        dfs(root, 0, curVal, curHeight);
        return curVal;
    }
};
